/*
	
	MultiLevelLayoutPlugin for Cytoscape (http://www.cytoscape.org/) 
	Copyright (C) 2007 Pekka Salmela

	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License
	as published by the Free Software Foundation; either version 2
	of the License, or (at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
	
 */

package multilevelLayoutPlugin;

import giny.model.Node;
import giny.view.NodeView;

import java.awt.GridLayout;
import java.util.Iterator;
import java.util.Vector;

import javax.swing.JPanel;

import cytoscape.CyEdge;
import cytoscape.CyNetwork;
import cytoscape.CyNode;
import cytoscape.Cytoscape;
import cytoscape.data.CyAttributes;
import cytoscape.layout.AbstractLayout;
import cytoscape.layout.LayoutProperties;
import cytoscape.layout.Tunable;
import cytoscape.view.CyNetworkView;

/**
 * Class executing the multilevel layout algorithm originally presented by C.
 * Walshaw (2003). The algorithm is slightly tuned by Pekka Salmela (2007). The
 * algorithm contains two main phases: 1) Construct a hierarchy of continuously
 * coarser graphs by finding maximal independent sets of edges on each level
 * until there are only two nodes and one edge left. 2) Starting from the
 * coarsest graph consisting, place the two nodes randomly and use the positions
 * to place nodes of the next graph in the hierarchy. Then adjust the positions
 * using a heavily tuned version of force-directed placement algorithm.
 * 
 * @author Pekka Salmela
 */

public class MultilevelLayoutAlgorithm extends AbstractLayout {

    private NodePositionManager posManager;
    private int level;
    protected boolean cancel = false;
    private LayoutProperties layoutProperties = null;
    public MultilevelConfig multilevelConfig = new MultilevelConfig();

    /**
     * Constructor.
     */
    public MultilevelLayoutAlgorithm() {
        super();
        layoutProperties = new LayoutProperties(getName());
        layoutProperties
                .add(new Tunable(
                        "repForceMultiplier",
                        "<html>Constant multiplier used in the calculation of repulsive forces. "
                                + "<br>&nbsp;&nbsp;&nbsp;&nbsp;Default value 0.2, suggested value 0.1 - 0.9.<br><br></html>",
                        Tunable.DOUBLE, new Double(0.2)));
        layoutProperties
                .add(new Tunable(
                        "tolMultiplier",
                        "<html>Parameter used to control the tolerance below which the algorithm is concidered to be converged. "
                                + "<br>&nbsp;&nbsp;&nbsp;&nbsp;Default value 0.01, suggested value 0.01 - 0.09.<br><br></html>",
                        Tunable.DOUBLE, new Double(0.01)));
        layoutProperties
                .add(new Tunable(
                        "clusteringOption",
                        "<html>Flag indicating if the clustering option should be used during layout calculation. "
                                + "<br>&nbsp;&nbsp;&nbsp;&nbsp;Used by default.<br><br></html>",
                        Tunable.BOOLEAN, Boolean.valueOf(true)));
        layoutProperties
                .add(new Tunable(
                        "springLenghtConstant",
                        "<html>Parameter used to control the natural spring length of the algorithm. The bigger the value the more \"tight\" the resulting layout will be. "
                                + "<br>&nbsp;&nbsp;&nbsp;&nbsp;Default value 4/7 (~0.5714), suggested value 0.5 - 0.8. If the layout algorithm terminates abnormally you can try sligthly bigger value for this parameter.<br><br></html>",
                        Tunable.DOUBLE, new Double(4.0 / 7.0)));

        layoutProperties
                .add(new Tunable(
                        "mTreeEnabled",
                        "<html>Flag indicating if M-trees should be used during the layout calculation. "
                                + "<br>&nbsp;&nbsp;&nbsp;&nbsp;Used by default.<br><br></html>",
                        Tunable.BOOLEAN, Boolean.valueOf(true)));

        layoutProperties
                .add(new Tunable(
                        "startLikeLayout",
                        "<html>Flag indicating whether the degree-weighted function is used in the node mathcing process. This may benefit drawing networks with 'star-like' structures."
                                + "<br>&nbsp;&nbsp;&nbsp;&nbsp;Not used by default.<br></html>",
                        Tunable.BOOLEAN, Boolean.valueOf(false)));

        // We've now set all of our tunables, so we can read the property
        // file now and adjust as appropriate
        layoutProperties.initializeProperties();

        // Finally, update everything. We need to do this to update
        // any of our values based on what we read from the property file
        updateSettings(true);
    }

    public MultilevelLayoutAlgorithm(final boolean clustering,
            final boolean mtree) {
        this();
        multilevelConfig.clusteringEnabled = clustering;
        multilevelConfig.mTreeEnabled = mtree;
    }

    /**
     * External interface to update our settings
     */
    @Override
    public void updateSettings() {
        updateSettings(true);
    }

    /**
     * Signal that we want to update our internal settings
     * 
     * @param force
     *            force the settings to be updated, if true
     */
    public void updateSettings(final boolean force) {
        layoutProperties.updateValues();
        final Tunable t1 = layoutProperties.get("repForceMultiplier");
        if (t1 != null) {
            multilevelConfig.C = ((Double) t1.getValue()).doubleValue();
        }
        final Tunable t2 = layoutProperties.get("tolMultiplier");
        if (t2 != null) {
            multilevelConfig.tolerance = ((Double) t2.getValue()).doubleValue();
        }
        final Tunable t3 = layoutProperties.get("clusteringOption");
        if (t3 != null) {
            multilevelConfig.clusteringEnabled = ((Boolean) t3.getValue())
                    .booleanValue();
        }
        final Tunable t6 = layoutProperties.get("springLenghtConstant");
        if (t6 != null) {
            multilevelConfig.springLengthConstant = ((Double) t6.getValue())
                    .doubleValue();
        }
        final Tunable t7 = layoutProperties.get("mTreeEnabled");
        if (t7 != null) {
            multilevelConfig.mTreeEnabled = ((Boolean) t7.getValue())
                    .booleanValue();
        }
        final Tunable t8 = layoutProperties.get("startLikeLayoutPrevention");
        if (t8 != null) {
            multilevelConfig.startLikeLayoutPrevention = ((Boolean) t8
                    .getValue()).booleanValue();
        }
    }

    /**
     * Revert our settings back to the original.
     */
    @Override
    public void revertSettings() {
        if (layoutProperties != null) {
            layoutProperties.revertProperties();
        }
    }

    @Override
    public LayoutProperties getSettings() {
        return layoutProperties;
    }

    /**
     * Main entry point for AbstractLayout classes. Initializes and runs the
     * algorithm.
     */
    @Override
    public void construct() {
        System.out.println("START:" + multilevelConfig.springLengthConstant);
        taskMonitor.setStatus("Initializing");
        initialize(); // Calls initialize_local
        try {
            executeLayout();
            networkView.fitContent();
            networkView.updateView();
        } catch (final IllegalStateException e) {
            // start over with bigger spring length constant
            if (multilevelConfig.springLengthConstant <= 0.7) {
                multilevelConfig.springLengthConstant = 0.79;
            } else if (multilevelConfig.springLengthConstant <= 0.8) {
                multilevelConfig.springLengthConstant = 0.85;
            } else {
                throw new RuntimeException(e);
            }
            construct();
        }
    }

    /**
     * Call all of the initialization code. Called from
     * <code>AbstractLayout.initialize()</code>.
     */
    @Override
    protected void initialize_local() {
        posManager = new NodePositionManager(networkView.getNetwork()
                .getNodeCount());
        level = 0;
    }

    /**
     * Execute layout algorithm.
     */
    @SuppressWarnings("unchecked")
    private void executeLayout() {
        final long start = System.currentTimeMillis();
        final CyNetworkView finalView = Cytoscape.getCurrentNetworkView();
        final CyNetwork origNetwork = networkView.getNetwork();
        final int originalSize = origNetwork.getNodeCount();

        if (cancel == true) {
            return;
        }

        final Vector<CyNetwork> components = quickSortNetworks(GraphConnectivityChecker
                .getGraphComponents(origNetwork));

        taskMonitor.setStatus("Finding independent sets...");
        taskMonitor.setPercentCompleted(5);
        int nodesSoFar = 0;

        for (final CyNetwork cn : components) {
            final Vector<CyNetwork> networkSet = new Vector<CyNetwork>(
                    (int) Math.sqrt(cn.getNodeCount()), 5);
            networkSet.add(cn);
            boolean goOn = true;
            // construct a set of continuously coarser graphs by calculating
            // maximum independent sets
            int nodeCount = cn.getNodeCount();
            if (nodeCount > 2) {
                while (goOn) {
                    final CyNetwork next = MaximalIndependentSetFinder
                            .findMaximalIndependentSet(
                                    networkSet.lastElement(), level,
                                    multilevelConfig.startLikeLayoutPrevention);

                    // final CyNetwork next = Kruskal.findMaximalIndependentSet(
                    // networkSet.lastElement(), level);
                    if (nodeCount != next.getNodeCount()) {
                        nodeCount = next.getNodeCount();
                        if (nodeCount == 2) {
                            goOn = false;
                        }
                        networkSet.add(next);
                        level++;
                    } else {
                        goOn = false;
                    }
                }
            }
            if (cancel == true) {
                for (int i = 1; i < networkSet.size(); i++) {
                    Cytoscape.destroyNetwork(networkSet.elementAt(i));
                }
                return;
            }

            taskMonitor.setStatus("Calculating the layout...");
            taskMonitor.setPercentCompleted(10);

            if (networkSet.size() == 1) {
                final Iterator<Node> iter = networkSet.elementAt(0)
                        .nodesIterator();
                int i = 1;
                while (iter.hasNext()) {
                    final Node n = iter.next();
                    posManager.addNode(n.getRootGraphIndex(), (i) * 30.0,
                            (i) * 30.0);
                    i++;
                }
            }

            CyNetwork currentNetwork = null;
            double previousNaturalSpringLength = 0.0;
            nodesSoFar += cn.getNodeCount();

            // starting from the coarsest graph, calculate enhanced
            // force-directed layout for each level
            while (networkSet.size() > 1) {
                if (cancel == true) {
                    for (int i = 1; i < networkSet.size(); i++) {
                        Cytoscape.destroyNetwork(networkSet.elementAt(i));
                    }
                    return;
                }
                level--;
                // if currentNetwork is not set, then this is the first level
                if (currentNetwork == null) {
                    currentNetwork = networkSet.lastElement();

                    final double dmax = 5.0 / (Math.pow(
                            Math.sqrt(multilevelConfig.springLengthConstant),
                            (level + 1)));
                    final Iterator<CyNode> iter = currentNetwork
                            .nodesIterator();
                    CyNode n = iter.next();
                    posManager.addNode(n.getRootGraphIndex(), dmax, 0.0);
                    n = iter.next();
                    posManager.addNode(n.getRootGraphIndex(), 0.0, dmax);
                    previousNaturalSpringLength = Math.sqrt(2.0) * dmax;

                }

                taskMonitor.setStatus("Calculating the layout on level "
                        + level + " for component "
                        + (components.indexOf(cn) + 1) + "/"
                        + (components.size()));
                taskMonitor.setPercentCompleted((int) (80.0
                        * (((double) nodesSoFar) / ((double) originalSize))
                        / (level + 2.0) + 10.0));

                // take the network before the last one from the list
                final CyNetwork nextNetwork = networkSet.elementAt(networkSet
                        .size() - 2);

                // use nextNetwork to place nodes in currentNetwork
                doOneLevelPlacement(currentNetwork, nextNetwork,
                        previousNaturalSpringLength);
                // use EFDL to nextNetwork
                final EnhancedForceDirectedLayout e = new EnhancedForceDirectedLayout(
                        previousNaturalSpringLength, level, nextNetwork,
                        posManager, multilevelConfig);
                e.doLayout();
                // store the natural spring length
                previousNaturalSpringLength = e.getK();
                // System.err.println("D :" + previousNaturalSpringLength);

                // remove used network from the list
                networkSet.remove(networkSet.size() - 1);

                // clean up (we can not use
                // Cytoscape.destroyNetwork(currentNetwork), because
                // currentNetwork has been created by
                // Cytoscape.getRootGraph.createNetwork(...)
                // and destroying raises an exception)
                final Iterator<CyNode> i1 = currentNetwork.nodesIterator();
                while (i1.hasNext()) {
                    final CyNode n = i1.next();
                    posManager.removeNode(n.getRootGraphIndex());
                    Cytoscape.getRootGraph().removeNode(n);
                }
                final Iterator<CyEdge> i2 = currentNetwork.edgesIterator();
                while (i2.hasNext()) {
                    Cytoscape.getRootGraph().removeEdge(i2.next());
                }

                // change the network to be used during the next iteration
                currentNetwork = nextNetwork;
            }
        }

        // iterate over node positions and apply them to the NetworkView
        taskMonitor.setStatus("Updating node positions...");
        taskMonitor.setPercentCompleted(95);

        // first scale the network to look good, or at least tolerable

        for (final CyNetwork cn : components) {
            double minX = Double.POSITIVE_INFINITY;
            double minY = Double.POSITIVE_INFINITY;
            double maxX = Double.NEGATIVE_INFINITY;
            double maxY = Double.NEGATIVE_INFINITY;
            Iterator<Node> iter = cn.nodesIterator();
            while (iter.hasNext()) {
                final Node n = iter.next();
                // NodeView nv = finalView.getNodeView(iter.next());
                if (posManager.getX(n.getRootGraphIndex()) < minX) {
                    minX = posManager.getX(n.getRootGraphIndex());
                }
                if (posManager.getY(n.getRootGraphIndex()) < minY) {
                    minY = posManager.getY(n.getRootGraphIndex());
                }
                if (posManager.getX(n.getRootGraphIndex()) > maxX) {
                    maxX = posManager.getX(n.getRootGraphIndex());
                }
                if (posManager.getY(n.getRootGraphIndex()) > maxY) {
                    maxY = posManager.getY(n.getRootGraphIndex());
                }
            }
            double xDifference = maxX - minX;
            if (xDifference == 0.0) {
                xDifference = 1.0;
            }
            double yDifference = maxY - minY;
            if (yDifference == 0.0) {
                yDifference = 1.0;
            }
            iter = cn.nodesIterator();
            while (iter.hasNext()) {
                final Node n = iter.next();
                posManager.setX(n.getRootGraphIndex(), ((300.0 * Math.sqrt(cn
                        .getNodeCount()) * (posManager.getX(n
                        .getRootGraphIndex()) - minX)) / (xDifference)));
                posManager.setY(n.getRootGraphIndex(), ((300.0 * Math.sqrt(cn
                        .getNodeCount()) * (posManager.getY(n
                        .getRootGraphIndex()) - minY)) / (yDifference)));
            }
        }

        taskMonitor.setStatus("Laying out the graph...");
        taskMonitor.setPercentCompleted(99);

        final Iterator<CyNetwork> iter = components.iterator();
        final CyNetwork first = iter.next();
        Iterator<Node> nodesIter = first.nodesIterator();
        double maxX = 0;
        double maxY = 0;
        while (nodesIter.hasNext()) {
            final Node n = nodesIter.next();
            final NodeView nv = finalView.getNodeView(n);
            nv.setXPosition(posManager.getX(n.getRootGraphIndex()));
            nv.setYPosition(posManager.getY(n.getRootGraphIndex()));
            if (nv.getXPosition() > maxX) {
                maxX = nv.getXPosition();
            }
            if (nv.getYPosition() > maxY) {
                maxY = nv.getYPosition();
            }
        }

        double rowMaxX = -100.0;
        double rowMaxY = maxY;
        while (iter.hasNext()) {
            final CyNetwork next = iter.next();
            nodesIter = next.nodesIterator();
            final double tempYLimit = maxY;
            final double tempXLimit = rowMaxX;
            while (nodesIter.hasNext()) {
                final Node n = nodesIter.next();
                final NodeView nv = finalView.getNodeView(n);
                nv.setXPosition(posManager.getX(n.getRootGraphIndex())
                        + tempXLimit + 100.0);
                nv.setYPosition(posManager.getY(n.getRootGraphIndex())
                        + tempYLimit + 100.0);
                if (nv.getXPosition() > rowMaxX) {
                    rowMaxX = nv.getXPosition();
                }
                if (nv.getYPosition() > rowMaxY) {
                    rowMaxY = nv.getYPosition();
                }
            }
            if (rowMaxX > maxX) {
                rowMaxX = -100.0;
                maxY = rowMaxY;
            }
        }

        System.out
                .println("Calculating the layout took "
                        + ((System.currentTimeMillis() - start) / 1000.0)
                        + " seconds.");

        final CyAttributes nodesAttributes = Cytoscape.getNodeAttributes();
        nodesAttributes
                .deleteAttribute(MaximalIndependentSetFinder.ML_PREVIOUS);
        nodesAttributes
                .deleteAttribute(MaximalIndependentSetFinder.ML_ANCESTOR1);
        nodesAttributes
                .deleteAttribute(MaximalIndependentSetFinder.ML_ANCESTOR2);
        nodesAttributes.deleteAttribute(MaximalIndependentSetFinder.ML_WEIGHT);

        taskMonitor.setPercentCompleted(100);
        taskMonitor.setStatus("Layout complete");
        posManager.clear();
        posManager = null;
        System.gc();
        System.out.println("Stop MultiLevelPlugin");
    }

    /**
     * Places the nodes of a more detailed graph using the positions of a
     * coarser graph. A position manager is used to store node positions and
     * node attributes are used to denote connections between nodes in different
     * graph levels.
     * 
     * @param coarser
     *            The graph determining the node positions.
     * @param finer
     *            The graph the placement is applied to.
     */
    @SuppressWarnings("unchecked")
    private void doOneLevelPlacement(final CyNetwork coarser,
            final CyNetwork finer, final double k) {
        // iterate over the nodes of the previous graph
        final Iterator<CyNode> nodesIterator = coarser.nodesIterator();
        final CyAttributes nodesAttributes = Cytoscape.getNodeAttributes();

        while (nodesIterator.hasNext()) {
            final CyNode n = nodesIterator.next();
            final double nX = posManager.getX(n.getRootGraphIndex());
            final double nY = posManager.getY(n.getRootGraphIndex());
            if (nodesAttributes.getIntegerAttribute(n.getIdentifier(),
                    MaximalIndependentSetFinder.ML_PREVIOUS) != null) {
                // place only one node
                final Integer pre = nodesAttributes.getIntegerAttribute(
                        n.getIdentifier(),
                        MaximalIndependentSetFinder.ML_PREVIOUS);
                posManager.addNode(pre, nX, nY);
            } else {
                // place two nodes
                final Integer anc1 = nodesAttributes.getIntegerAttribute(
                        n.getIdentifier(),
                        MaximalIndependentSetFinder.ML_ANCESTOR1);
                final Integer anc2 = nodesAttributes.getIntegerAttribute(
                        n.getIdentifier(),
                        MaximalIndependentSetFinder.ML_ANCESTOR2);
                posManager.addNode(anc1, nX, nY);
                posManager.addNode(anc2, nX + plusOrMinusOne() * 0.001 * k, nY
                        + plusOrMinusOne() * 0.001 * k);
            }
        }
    }

    /**
     * Sorts a vector of networks in ascending order according to network sizes.
     * 
     * @param networks
     *            Vector of networks to be sorted
     * @return A new vector containing all the original networks in sorted
     *         order.
     */
    private Vector<CyNetwork> quickSortNetworks(final Vector<CyNetwork> networks) {
        if (networks.size() <= 1) {
            return networks;
        }
        final Vector<CyNetwork> less = new Vector<CyNetwork>();
        final Vector<CyNetwork> pivotList = new Vector<CyNetwork>();
        final Vector<CyNetwork> greater = new Vector<CyNetwork>();
        final int pivot = networks.elementAt(
                (int) (Math.random() * networks.size())).getNodeCount();
        for (final CyNetwork cn : networks) {
            if (cn.getNodeCount() < pivot) {
                less.add(cn);
            }
            if (cn.getNodeCount() == pivot) {
                pivotList.add(cn);
            }
            if (cn.getNodeCount() > pivot) {
                greater.add(cn);
            }
        }
        final Vector<CyNetwork> result = new Vector<CyNetwork>();
        result.addAll(quickSortNetworks(greater));
        result.addAll(pivotList);
        result.addAll(quickSortNetworks(less));
        return result;
    }

    /**
     * Returns a JPanel to be used as part of the Settings dialog for this
     * layout algorithm.
     * 
     */
    @Override
    public JPanel getSettingsPanel() {
        final JPanel panel = new JPanel(new GridLayout(0, 1));
        panel.add(layoutProperties.getTunablePanel());
        return panel;
    }

    /**
     * Returns 1 or -1 with equal probability.
     * 
     * @return 1 or -1, toss a coin to guess which one.
     */
    private double plusOrMinusOne() {
        if (Math.random() < 0.5) {
            return 1.0;
        } else {
            return -1.0;
        }
    }

    /**
     * Return the short-hand name of this algorithm
     * 
     * @return short-hand name
     */
    @Override
    public String getName() {
        return "multilevel-layout";
    }

    /**
     * Return the user-visible name of this layout
     * 
     * @return user visible name
     */
    @Override
    public String toString() {
        return "Multilevel Layout";
    }

    /**
     * Return true if we support performing our layout on a limited set of nodes
     * 
     * @return true if we support selected-only layout
     */
    @Override
    public boolean supportsSelectedOnly() {
        return false;
    }

    @Override
    public byte[] supportsNodeAttributes() {
        return null;
    }

    @Override
    public byte[] supportsEdgeAttributes() {
        return null;
    }

    /**
     * Tells the algorithm it should be aborted.
     * 
     */
    public void setCancel() {
        cancel = true;
    }
}
